package com.antball.data.insert;

import java.util.Arrays;

/**
 * @Auther: huangsj
 * @Date: 2019/9/18 11:27
 * @Description:
 */
public class ShellInsertSort {

    public static void shellSort(int[] arr) {
        int i, j, gap;
        // 获得步长
        for (gap = arr.length / 2; gap > 0; gap /= 2) {
            System.out.println("gap:"+gap);
            // 进行插入排序
            for (i = 0; i < gap; i++) {
                // j每个子列表元素下标
                for (j = i + gap; j < arr.length; j += gap) {
                    //  比较子列表元素值大小 直接插入排序
                    if (arr[j] < arr[j - gap]) {
                        int tmp = arr[j];
                        int k = j - gap;
                        while (k >= 0 && arr[k] > tmp) {
                            arr[k + gap] = arr[k];
                            k -= gap;
                        }
                        arr[k + gap] = tmp;
                        System.out.println(Arrays.toString(arr));
                    }

                }
            }
        }
    }


    public static void main(String[] args) {
//        int[] a= new int[]{2,5,3,7};

        int[] a = {7, 2, 5, 3, 1, 9, 4};
        System.out.println(Arrays.toString(a));
        shellSort(a);
    }
}
